División de Cadenas

   Cierto lenguaje de procesamiento de cadenas le permite a los programadores dividir una cadena en dos partes. Debido a que esto implica copiar la cadena original, el costo de dividir en dos una cadena de k caracteres es de k unidades de tiempo.

Suponga que un programadis desea dividir unacadena S en N partes de longitud A1, A2 , ...,AN respectivamente. El orden en que se hagan las divisionespuede afectar la cantidad total de tiempo que se necesita para dividir la cadena.

   Escribe un programa que determine la cantidad mínima de tiempo T que se requiere para dividir la cadena. Por ejemplo, la cadena OLIMPIADAINFORMATICA y se quiere dividir en las cinco cadenas OLIMP, PIA, DAIN, FORMA y TICA entonces se requiere un mínimo de 47 unidades de tiempo, haciendo las divisiones como sigue: primero se hace la división OLIMPIADAIN - FORMATICA ( costo 20 ), depues la división OLIM - PIADAIN (costo 11), posteriormente la division la división PIA - DAIN ( costo 7 )  y finalmente FORMA - TIA (costo 9).

Entrada
   El archivo "Input.txt" contiene en el prmer renglón la cantidad N de partes (0 < N < 101) y en el segundo renglón la lista de longitudes de las partes A1, A 2, ...,AN con ( 0 < Ai < 1001)

Salida
   El archivo "Output.txt" debe´ra contener en el primer renglón al entero T.

Input.txt
Output.txt
5
4 3 5 4 4
47

 


 

Regresar